package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * LC17.电话号码的字母组合
 */
public class LC17 {
    private static Map<Character, List<Character>> keyBoard = new HashMap<>();
    static {
        keyBoard.put('2', List.of('a', 'b', 'c'));
        keyBoard.put('3', List.of('d', 'e', 'f'));
        keyBoard.put('4', List.of('g', 'h', 'i'));
        keyBoard.put('5', List.of('j', 'k', 'l'));
        keyBoard.put('6', List.of('m', 'n', 'o'));
        keyBoard.put('7', List.of('p', 'q', 'r', 's'));
        keyBoard.put('8', List.of('t', 'u', 'v'));
        keyBoard.put('9', List.of('w', 'x', 'y', 'z'));
    }
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits.isEmpty()) {
            return ans;
        }
        StringBuilder trace = new StringBuilder();
        backtracking(0, digits, trace, ans);
        return ans;
    }

    private void backtracking(int start, String digits, StringBuilder trace, List<String> ans) {
        if (start == digits.length()) {
            ans.add(trace.toString());
            return;
        }
        List<Character> letters = keyBoard.get(digits.charAt(start));
        for (Character letter : letters) {
            trace.append(letter);
            backtracking(start + 1, digits, trace, ans);
            trace.deleteCharAt(trace.length() - 1);
        }
    }

    public static void main(String[] args) {
        LC17 alg = new LC17();
        System.out.println(alg.letterCombinations("23"));
    }
}
